package com.leetcode.p200;

import java.util.TreeSet;

public class Test220 {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> st = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            Long ceilingData = st.ceiling((long) nums[i]);  //>=nums[i] 最接近  nums[i]的值
            Long floorData = st.floor((long) nums[i]);   //<=nums[i] 最接近  nums[i]的值

            if (ceilingData != null && ceilingData - nums[i] <= t) return true;
            if (floorData != null && nums[i] - floorData <= t) return true;

            st.add((long) nums[i]);

            if (st.size() > k) {
                st.remove((long) (nums[i - k]));
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 5, 9, 1, 5, 9};

        Test220 test = new Test220();
        boolean result = test.containsNearbyAlmostDuplicate(arr, 1, 4);
        System.out.println(result);
    }

}
